/*
   @Copyright:LintCode
   @Author:   tjyemail
   @Problem:  http://www.lintcode.com/problem/rotate-words
   @Language: C++
   @Datetime: 19-04-25 09:27
   */

class Solution {
	size_t hashcode(const string &s)const{
		int pos=0;
		for(int i=s.length(); i--; pos=s[pos]<s[i]?pos:i);
		vector<int> poss;
		for(int i=s.length(); i--;)
			if(s[i]==s[pos]) poss.push_back(i);
		string str;
		for(const int &i:poss){
			string tmp;
			tmp.append(s.substr(i));
			tmp.append(s.substr(0,i));
			if(str.length()<1 || greater<string>()(str,tmp)) str=tmp;
		}
		return hash<string>()(str);
	}

public:
	/*
	 * @param words: A list of words
	 * @return: Return how many different rotate words
	 */
	int countRotateWords(vector<string> words) {
		// Write your code here
		unordered_set<int> dict;
		for(const string &word:words)
			dict.insert(hashcode(word));
		return dict.size();
	}
};
